#include "digraph.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_MULT  314159     /* random multiplier */
#define HASH_PRIME 516595003  /* the 27182818th prime; it's less than $2^{29}$ */
#define maxV 1023
#define URL_SIZE 256

//static Vertex hash_head[maxV];
//static Vertex hash_link[maxV];

/* http:.../~pf/algoritmos_para_grafos/aulas/digraphdatastructs.html */

/* Esta função devolve (o endereço de) um novo digrafo com 
   vértices 0,..,V-1 e nenhum arco. */

Digraph DIGRAPHinit (int V)
{ 
  Vertex v;

  Digraph G = malloc(sizeof *G);
  G->V = V; 
  G->A = 0;
  G->out = malloc(V * sizeof(int));
  G->dng = malloc(V * sizeof(int));
  G->adj = malloc(V * sizeof(link));
  G->URL = malloc(V * sizeof(char *));
  for (v = 0; v < V; v++) {
    G->adj[v] = NULL;
    G->out[v] = 0;
    G->dng[v] = 1;
    G->URL[v] = malloc(URL_SIZE * sizeof(char));
  }
  return G;
}


link NEW (Vertex w, link next)
{
  link x = malloc(sizeof *x);

  x->w = w;
  x->next = next;
  return x;
}

void DIGRAPHurl (Digraph G, Vertex v, char *url)
{
  G->URL[v] = strcpy(G->URL[v], url);
}

/* Esta função insere um arco v-w no digrafo G. 
   Se v == w ou o digrafo já tem arco v-w, a função não faz nada.  
   É claro que v e w não podem ser negativos e devem ser menores que G->V. */

void DIGRAPHinsertA (Digraph G, Vertex v, Vertex w)
{
  if (v == w) return;
  G->adj[v] = NEW(w, G->adj[v]);
  G->out[v]++;
  G->dng[v] = 0;
  G->A++;
}

/* Esta função remove do digrafo G o arco que tem ponta inicial 
   v e ponta final w.  Se não existe tal arco, a função nada faz. */

void DIGRAPHremoveA (Digraph G, Vertex v, Vertex w)
{
  //TODO
}

/* Para cada vértice v do digrafo G, esta função imprime,
   em uma linha, todos os vértices adjacentes a v. */

void DIGRAPHshow (Digraph G)
{ 
  Vertex v;
  link p;

  printf("V = %d\n", G->V);
  printf("A = %d\n", G->A);
  for (v = 0; v < G->V; v++) {
    printf("%3d:", v);
    for (p = G->adj[v]; p != NULL; p = p->next) {
      printf(" %3d", p->w);
    }
    printf("\n");
  }
}

void DIGRAPHfree (Digraph G)
{
  Vertex v;

  for (v = 0; v < G->V; v++) {
    free_list(G->adj[v]);
  }
  free(G->adj);
  free(G->out);
  free(G->dng);
  free(G);
}

void free_list (link list)
{
  link p, q;
  if (list == NULL) return;
  p = list;
  q = list->next;
  if (q != NULL) {
    free_list(q);
    p->next = NULL;
    free(p);
  }
  if (q == NULL) {
    free(p);
  }
}

